Corelab Seminar
2018-2019
Konstantinos Georgiou
Energy Consumption of Group Search on a Line
Abstract.
Consider two robots that start at the origin of the infinite line in search
of an exit at an unknown location on the line. The robots can collaborate
in the search, but can only communicate if they arrive at the same location
at exactly the same time, i.e. they use the so-called face-to-face
communication model. The group search time is defined as the worst-case
time as a function of $d$, the distance of the exit from the origin, when
both robots can reach the exit. It has long been known that for a single
robot traveling at unit speed, the search time is at least $9d - o(d)$; a
simple doubling strategy achieves this time bound. It was shown recently in
that $k \geq 2$ robots traveling at unit speed also require at least $9d$
group search time.
We investigate energy-time trade-offs in group search by two robots, where
the energy loss experienced by a robot traveling a distance $x$ at constant
speed $s$ is given by $s^2 x$, as motivated by energy consumption models in
physics and engineering. Specifically, we consider the problem of
minimizing the total energy used by the robots, under the constraints that
the search time is at most a multiple $c$ of the distance $d$ and the speed
of the robots is bounded by $b$. Motivation for this study is that for the
case when robots must complete the search in $9d$ time with maximum speed
one ($b=1;~c=9$), a single robot requires at least $9d$ energy, while for
two robots, all previously proposed algorithms consume at least $28d/3$
energy.
When the robots have bounded memory and can use only a constant number of
fixed speeds, we generalize known algorithms to obtain a family of
algorithms parametrized by pairs of $b,c$ values that can solve the problem
for the entire spectrum of these pairs for which the problem is solvable.
In particular, for each such pair, we determine optimal (and in some cases
nearly optimal) algorithms inducing the lowest possible energy consumption.
We also propose a novel search algorithm that simultaneously achieves
search time $9d$ and consumes energy $8.42588d$. Our algorithm uses robots
that have unbounded memory, and a finite number of dynamically computed
speeds.
Short Bio:
Konstantinos Georgiou is an Assistant Professor at Ryerson University. He
holds a Bachelor's in Mathematics and a MSc in Theoretical Computer Science
from the University of Athens, and a PhD from the University of
Toronto. His research interests span Combinatorial Optimization, Mobile
Agent Computing and Game Theory.